| 翻訳と辞書 |
| Herschel graph ： ウィキペディア英語版 |
Herschel graph
In graph theory, a branch of mathematics, the Herschel graph is a bipartite undirected graph with 11 vertices and 18 edges, the smallest non-Hamiltonian polyhedral graph. It is named after British astronomer Alexander Stewart Herschel, who wrote an early paper concerning William Rowan Hamilton's icosian game: the Herschel graph describes the smallest convex polyhedron for which this game has no solution. However, Herschel's paper described solutions for the Icosian game only on the graphs of the regular tetrahedron and regular icosahedron; it did not describe the Herschel graph.〔.〕
==Properties==
The Herschel graph is a planar graph: it can be drawn in the plane with none of its edges crossing. It is also 3-vertex-connected: the removal of any two of its vertices leaves a connected subgraph. Therefore, by Steinitz's theorem, the Herschel graph is a polyhedral graph: there exists a convex polyhedron (an enneahedron) having the Herschel graph as its skeleton.〔.〕
The Herschel graph is also a bipartite graph: its vertices can be separated into two subsets of five and six vertices respectively, such that every edge has an endpoint in each subset (the red and blue subsets in the picture).
As with any bipartite graph, the Herschel graph is a perfect graph : the chromatic number of every induced subgraph equals the size of the largest clique of that subgraph. It has also chromatic index 4, girth 4, radius 3 and diameter 4.
抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』
■ウィキペディアで「Herschel graph」の詳細全文を読む
スポンサード リンク
| 翻訳と辞書 : 翻訳のためのインターネットリソース |
Copyright(C) kotoba.ne.jp 1997-2016. All Rights Reserved.
|
|